package mao.leetcode.dp.leetcode300;

import java.util.Arrays;

public class Solution {

    //效率有点低
    public int lengthOfLIS_1(int[] nums) {
        if (nums.length == 0) return 0;
        int[] LIS = new int[nums.length];
        int ans=1;
        Arrays.fill(LIS,1);
        for (int i = 1; i < nums.length; i++){
            for (int j = i-1; j >= 0; j--) {
                if (nums[j]<nums[i]) {
                    LIS[i] = Math.max(LIS[i], LIS[j]+1);
                }
            }
            ans = Math.max(ans,LIS[i]);
        }
        return ans;
    }

    //漂亮
    public static int lengthOfLIS(int[] nums) {
       int[] dp = new int[nums.length];
       int len=0;
        for (int i = 0; i < nums.length; i++) {
            int minimalTail = Arrays.binarySearch(dp, 0, len, nums[i]);
            if (minimalTail < 0) { //没有查找到；
                minimalTail=-(minimalTail+1);
                dp[minimalTail] = nums[i];
                if (minimalTail == len) len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] a = {10,9,2,5,3,7,101,18};
        lengthOfLIS(a);
    }
}
